package beans;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    /**
     * 1. 创建树形结构
     *
     * @param exp
     * @return
     */
    public static TreeNode parseToTreeNode(String exp) {
        String[] items = exp.replaceAll("[\\[\\]]", "").split(",");
        return initTree(items, 0);
    }

    private static TreeNode initTree(String[] items, int idx) {
        if (idx >= items.length || items[idx].equals("null")) {
            return null;
        }
        TreeNode node = new TreeNode();
        node.val = Integer.parseInt(items[idx]);
        node.left = initTree(items, idx * 2 + 1);
        node.right = initTree(items, (idx + 1) * 2);
        return node;
    }


    /**
     * 2. 使用前序和中序构建树
     *
     * @param pre
     * @param mid
     * @return
     */
    public static TreeNode parseToTreeFromPreAndMid(String pre, String mid) {
        List<Integer> preList = Arrays.stream(pre.split("\\s+")).map(Integer::parseInt).collect(Collectors.toList());
        List<Integer> midList = Arrays.stream(mid.split("\\s+")).map(Integer::parseInt).collect(Collectors.toList());
        return parseToTreeFromPreAndMid(preList, midList);
    }


    public static TreeNode parseToTreeFromPreAndMid(List<Integer> pre, List<Integer> mid) {
        if (pre.size() > 0) {
            int val = pre.get(0);
            int idx = 0;
            while (idx < mid.size()) {
                if (mid.get(idx++) == val) {
                    break;
                }
            }
            // 左
            List<Integer> midLeft = mid.subList(0, idx - 1);
            List<Integer> midRight = mid.subList(idx, mid.size());
            List<Integer> preLeft = pre.subList(1, 1 + midLeft.size());
            List<Integer> preRight = pre.subList(preLeft.size() + 1, pre.size());
            TreeNode leftNode = parseToTreeFromPreAndMid(preLeft, midLeft);
            TreeNode rightNode = parseToTreeFromPreAndMid(preRight, midRight);
            TreeNode node = new TreeNode();
            node.val = val;
            node.left = leftNode;
            node.right = rightNode;
            return node;
        }
        return null;
    }


    @Override
    public String toString() {
        return "{" + val +
                "L[" + left +
                "], R[" + right +
                ']';
    }
}
